﻿using System;
using System.Linq;
using ParserGenerator.Collections;
using ParserGenerator.SyntacticAnalysis;

namespace ParserGenerator.GrammarAnalysis
{
    [Serializable]
    internal sealed class RecursiveLexicalAliasSimplifier
    {
        private readonly LexicalAliasTable _table;

        public RecursiveLexicalAliasSimplifier(LexicalAliasTable table)
        {
            if (table == null)
                throw new ArgumentNullException(nameof(table));
            _table = table;
        }

        private Sequence<Sequence<LexicalExpression>> GetBranches(LexicalExpression n)
        {
            if (n == null)
                throw new ArgumentNullException(nameof(n));
            Sequence<LexicalExpression> branches = n.ToUnionOperands();
            return Sequence.New(from x in branches select x.ToConcatOperands());
        }

        public void TrySimplify(LexicalAlias entry)
        {
            if (entry == null)
                throw new ArgumentNullException(nameof(entry));
            if (!entry.Pattern.IsUnion)
                return;
            var left = Sequence.GetEmpty<Sequence<LexicalExpression>>();
            var right = Sequence.GetEmpty<Sequence<LexicalExpression>>();
            var other = Sequence.GetEmpty<Sequence<LexicalExpression>>();
            var branches = GetBranches(entry.Pattern);
            foreach (Sequence<LexicalExpression> branch in branches)
            {
                bool isLeft = IsDirectRecursive(branch, entry, true);
                bool isRight = IsDirectRecursive(branch, entry, false);
                if (isLeft && isRight)
                    return;
                else if (isLeft)
                    left = Sequence.Append(left, branch);
                else if (isRight)
                    right = Sequence.Append(right, branch);
                else
                    other = Sequence.Append(other, branch);
            }
            if (left.Count > 0 && right.Count > 0)
                return;
            if (left.Count == 0 && right.Count == 0)
                return;
            if (other.Count == 0)
                return;
            LexicalExpression otherExpr = CreateUnionExpression(other);
            LexicalExpression newExpr;
            if (left.Count > 0)
            {
                LexicalExpression leftExpr = RemoveDirectRecursion(left, true);
                LexicalExpression starExpr = LexicalExpression.NewKleene(leftExpr);
                newExpr = LexicalExpression.NewConcat(otherExpr, starExpr);
            }
            else
            {
                LexicalExpression rightExpr = RemoveDirectRecursion(right, false);
                LexicalExpression starExpr = LexicalExpression.NewKleene(rightExpr);
                newExpr = LexicalExpression.NewConcat(starExpr, otherExpr);
            }
            entry.UpdatePattern(newExpr);
        }

        private bool IsDirectRecursive(Sequence<LexicalExpression> branch, LexicalAlias entry, bool checkLeft)
        {
            if (branch == null)
                throw new ArgumentNullException(nameof(branch));
            if (entry == null)
                throw new ArgumentNullException(nameof(entry));
            if (branch.Count >= 2)
            {
                LexicalExpression operand = branch[checkLeft ? 0 : branch.Count - 1];
                if (operand.IsNameReference)
                {
                    NameReferenceLexicalExpression e = operand.AsNameReference;
                    LexicalAlias alias = _table.Lookup(e.Name.Name, e.Context);
                    return alias == entry;
                }
            }
            return false;
        }

        private LexicalExpression RemoveDirectRecursion(Sequence<Sequence<LexicalExpression>> branches, bool removeLeft)
        {
            if (branches == null)
                throw new ArgumentNullException(nameof(branches));
            if (removeLeft)
                branches = branches.Map(x => x.RemoveAt(0));
            else
                branches = branches.Map(x => x.RemoveAt(x.Count - 1));
            return CreateUnionExpression(branches);
        }

        private LexicalExpression CreateUnionExpression(Sequence<Sequence<LexicalExpression>> branches)
        {
            if (branches == null)
                throw new ArgumentNullException(nameof(branches));
            Sequence<LexicalExpression> operands = branches.Map(x => CreateConcatExpression(x));
            return LexicalExpression.FromUnionOperands(operands);
        }

        private LexicalExpression CreateConcatExpression(Sequence<LexicalExpression> terms)
        {
            if (terms == null)
                throw new ArgumentNullException(nameof(terms));
            return LexicalExpression.FromConcatOperands(terms);
        }
    }
}

namespace ParserGenerator.SyntacticAnalysis
{
    partial class LexicalExpression
    {
        public static LexicalExpression FromConcatOperands(Sequence<LexicalExpression> operands)
        {
            if (operands == null)
                throw new ArgumentNullException(nameof(operands));
            if (operands.Count == 0)
                return NewEmpty();
            LexicalExpression n = operands[0];
            for (int i = 1; i < operands.Count; i++)
                n = NewConcat(n, operands[i]);
            return n;
        }

        public static LexicalExpression FromUnionOperands(Sequence<LexicalExpression> operands)
        {
            if (operands == null)
                throw new ArgumentNullException(nameof(operands));
            if (operands.Count == 0)
                return NewEmpty();
            LexicalExpression n = operands[0];
            for (int i = 1; i < operands.Count; i++)
                n = NewUnion(n, operands[i]);
            return n;
        }

        public Sequence<LexicalExpression> ToConcatOperands()
        {
            if (IsEmpty)
                return Sequence.GetEmpty<LexicalExpression>();
            if (!IsConcat)
                return Sequence.Create(this);
            ConcatLexicalExpression n = AsConcat;
            Sequence<LexicalExpression> operands = Sequence.Create(n.Right);
            while (n.Left.IsConcat)
            {
                n = n.Left.AsConcat;
                operands = Sequence.Prepend(n.Right, operands);
            }
            if (!n.Left.IsEmpty)
                operands = Sequence.Prepend(n.Left, operands);
            return operands;
        }

        public Sequence<LexicalExpression> ToUnionOperands()
        {
            if (IsEmpty)
                return Sequence.GetEmpty<LexicalExpression>();
            if (!IsUnion)
                return Sequence.Create(this);
            UnionLexicalExpression n = AsUnion;
            Sequence<LexicalExpression> operands = Sequence.Create(n.Right);
            while (n.Left.IsUnion)
            {
                n = n.Left.AsUnion;
                operands = Sequence.Prepend(n.Right, operands);
            }
            if (!n.Left.IsEmpty)
                operands = Sequence.Prepend(n.Left, operands);
            return operands;
        }
    }
}
